package com.sicheng.lc.周赛.分类.思维.数论;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/6 11:39
 */
public class 相同元素的间隔之和 {
    //https://leetcode.cn/problems/intervals-between-identical-elements/


    public long[] getDistances(int[] nums) {
        //间隔和
        //p是某个值的所有索引位置
        //p = [1, 3, 5, 10]
        //F[0] = 1 - 1 + 3 - 1 + 5 - 1 + 10 -1
        //F[1] = 3 - 1 + 3 - 3 + 5 - 3 + 10 - 3
        //说明：|a- b|，a表示第一项，b表示第二项；
        //因此，对应F[0]到F[1]，第一项增加了1 *( p[1] - p[0])，即(1-1) ->(3-1)，第二项减少了3*(p[1] - p[0])，(3-1)->(3-3)...；
        //依次类推，F[i] = F[i-1] + (2i -n) * (p[i] - p[i-1])
        HashMap<Integer, List<Integer>> map = new HashMap<>((int) 1e5);
        for (int i = 0; i < nums.length; i++) {
            map.computeIfAbsent(nums[i], k -> new ArrayList<>(1000)).add(i);
        }

        long[] res = new long[nums.length];
        for (List<Integer> p : map.values()) {
            int n = p.size();

            long f = 0;
            for (int i = 1; i < p.size(); i++) {
                f += Math.abs(p.get(i) - p.get(0));
            }
            res[p.get(0)] = f;
            for (int i = 1; i < p.size(); i++) {
                f = f - (n - 2L * i) * (p.get(i) - p.get(i - 1));
                res[p.get(i)] = f;
            }
        }
        return res;
    }
}
